package club.xiaojiawei.monotonestack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/12/22 3:37 PM
 * @question 503. 下一个更大元素 II
 * @description 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
 * 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
 */
public class NextGreaterElements503 {

    public static void main(String[] args) {
        NextGreaterElements503 test = new NextGreaterElements503();
        int[] result = test.nextGreaterElements(new int[]{1, 2, 3, 4, 3});
        System.out.println(Arrays.toString(result));
    }

    /**
     * 官方-单调栈 + 循环数组
     * 时间复杂度: O(n)
     * 空间复杂度: O(n)
     * @param nums
     * @return
     */
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);
        }
        return ret;
    }

    /**
     * 民间-
     * @param nums
     * @return
     */
    public int[] nextGreaterElements2(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        int[] res = new int[len];
        dp[len-1] = -1;
        for(int i = 0; i < len-1; i++){
            if(nums[len-1] < nums[i]){
                dp[len-1] = i;
                break;
            }
        }
        //从后向前构建一次dp，找到不考虑循环的第一个大于nums[i]的下标dp[i]
        for(int i = len-2; i >= 0; i--){
            if(nums[i] < nums[i+1])dp[i] = i + 1;
            else{
                int cursor = dp[i+1];
                //如果num[i+1]比nums[i]小，那去找第一个比nums[i+1]大的位置dp[i+1]，判断nums[dp[i+1]]是否大于nums[i]，以此类推，直到遍历到的位置已经向右没有更大元素
                while(cursor != -1 && cursor > i){
                    if(nums[cursor] > nums[i]){
                        dp[i] = cursor;
                        break;
                    }else{
                        cursor = dp[cursor];
                    }
                }
                //由于是向右判断第一个更大元素，dp[i]不可能为0;
                if(dp[i] == 0)dp[i] = -1;
            }
        }
        int cursor = 0;
        for(int i = len-2; i > 0; i--){
            if(dp[i] != -1)continue;
            while(cursor != -1 && cursor < i){
                if(nums[cursor] > nums[i]){
                    dp[i] = cursor;
                    break;
                }
                cursor = dp[cursor];
            }
        }
        for(int i = 0; i < len; i++){
            res[i] = -1 == dp[i] ? -1 : nums[dp[i]];
        }
        return res;
    }
}
